/*************************************************************
 * 
 * CopyRight(c)2007, http://www.moorwind.com/
 * email:ezhung@gmail.com
 * for free, but a email permission would be nice
 * 
 ************************************************************/
package kono.utils.sort
{
	public class Sort
	{
		public function Sort(){}
		
		public static function selectionSort (source:Array, start:uint, size:uint):void
		{
			if(size == 0)
				return;
			var i:uint, j:uint, big:uint;
			var temp:Number;
			for(i = size - 1; i > 0; i--)
			{
				big = start;
				for(j = start + 1; j <= start + i; j++)
				{
					if(source[j] > source[big])
						big = j;
				}
				temp = source[start + i];
				source[start + i] = source[big];
				source[big] = temp;
			}
		}
		
		public static function insertionSort(source:Array, start:uint, size:uint):void
		{
			if(size == 0)
				return ;
			var i:uint, j:uint;
			var temp:Number;
			for(i = 1; i < size; i++)
			{
				temp = source[start + i];
				for(j = start + i; source[j - 1] > temp && j > start; j--)
				{
					source[j] = source[j - 1];
					
				}
				source[j] = temp;
			}
		}
		
		public static function mergeSort(source:Array, start:uint, size:uint):void
		{
			if(size == 0)
				return ;
			var n1:uint, n2:uint;
			if(size > 1)
			{
				n1 = size / 2;
				n2 = size - n1;
				
				mergeSort(source,start,n1);
				mergeSort(source,start + n1,n2);
				
				merge(source, start, n1, n2);
			}
		}
		
		private static function merge(source:Array, start:uint, n1:uint, n2:uint):void
		{
			var temp:Array = new Array(n1 + n2);
			var copyed:uint = 0, copyed1:uint = 0, copyed2:uint = 0;
			while((copyed1 < n1) && (copyed2 < n2))
			{
				if(source[start + copyed1] < source[start + n1 + copyed2])
					temp[copyed++] = source[start + (copyed1++)];
				else
					temp[copyed++] = source[start + n1 + (copyed2++)];
			}
			while(copyed1 < n1)
				temp[copyed++] = source[start + (copyed1++)];
			while(copyed2 < n2)
				temp[copyed++] = source[start + n1 + (copyed2++)];
			
			for(var i:uint = 0; i < n1 + n2; i++)
				source[start + i] = temp[i];
		}
		
		public static function quickSort(source:Array, start:uint, size:uint):void
		{
			var pivotIndex:uint;
			var n1:uint, n2:uint;
			if(size == 0)
				return ;
			else
			{
				pivotIndex = partition(source,start,size);
				n1 = pivotIndex - start;
				n2 = size - n1 -1;
				
				quickSort(source,start,n1);
				quickSort(source, pivotIndex + 1, n2);
			}
		}
		
		private static function partition(source:Array, start:uint, size:uint):uint
		{
			var pivot:Number = source[start];
			var tooBigIndex:uint = start + 1;
			var tooSmallIndex:uint = start + size -1;
			var temp:Number;
			while(tooBigIndex <= tooSmallIndex)
			{
				if((tooBigIndex < source.length) && (source[tooBigIndex] <= pivot))
					tooBigIndex++;
				if(source[tooSmallIndex] > pivot)
					tooSmallIndex--;
				if(tooBigIndex < tooSmallIndex)
				{
					temp = source[tooSmallIndex];
					source[tooSmallIndex] = source[tooBigIndex];
					source[tooBigIndex] = temp;
				}				
			}
			temp = source[tooSmallIndex];
			source[start] = source[tooSmallIndex];
			source[tooSmallIndex] = pivot;
			return tooSmallIndex;
		}
	}
}